# # -*- coding:utf-8 -*-
# # class TreeNode:
# #     def __init__(self, x):
# #         self.val = x
# #         self.left = None
# #         self.right = None
# class Solution:
#     # 返回二维列表，内部每个列表表示找到的路径
#
#     def FindPath(self, root, expectNumber):
#         # write code here
#         def helper(res_list, root, expectNumber):
#             if not root:
#                 return []
#             res = []
#             if root.val < expectNumber:
#                 res_list.append(root)
#                 res.extend(helper(res_list[:], root.left, expectNumber-root.val))
#                 res.extend(helper(res_list[:], root.right, expectNumber-root.val))
#             elif root.val == expectNumber:
#                 res.append(root)
#             return res
#         if not root:
#             return [[]]
#         res = []
#         if root.val < expectNumber:
#             res.append(helper([root], root.left, expectNumber-root.val))
#             res.append(helper([root], root.right, expectNumber-root.val))
#             num_list = [len(one_res) for one_res in res]
#             num_list = sorted(enumerate(num_list), key=lambda  x: x[1], reverse=True)
#             return_res = []
#             for num in num_list:
#                 if num[1]:
#                     return_res.append(res(num[0]))
#             return return_res
#
#         elif root.val == expectNumber:
#             res.append([root])
#             return res
#         else:
#             res.append([])
#             return res
#
#
# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        if not root:
            return []

        ret = []  # 函数返回的二维列表
        path = []  # 遍历过程中经历的路径，假如符合条件，就加入到ret列表中
        self.Find(root, expectNumber, ret, path)
        return ret

    def Find(self, root, target, ret, path):
        if not root:
            return

        path.append(root.val)
        isLeaf = root.left is None and root.right is None
        print(path)
        if isLeaf and target == root.val:
            print('test')
            ret.append(path[:])  # 对于叶子节点，加上符合条件的path.`1
            print('ret is {}'.format(ret))
        if root.left:
            self.Find(root.left, target - root.val, ret, path)
        if root.right:
            self.Find(root.right, target - root.val, ret, path)

        path.pop()# 只有在到底的时候才会跑这一步
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(12)
left = root.left
left.left = TreeNode(4)
left.right = TreeNode(7)
test = Solution()
print(test.FindPath(root, 22))